package com.practice.niuke.new_direct_practice.class20;

import java.util.Arrays;

/**
 * 给定一个数组arr， 长度为N且每个值都是正数， 代表N个人的体重。 再给定一个正数
 * limit， 代表一艘船的载重。
 * 以下是坐船规则， 1)每艘船最多只能做两人;2)乘客 的体重和不能超过limit。
 * 返回如果同时让这N个人过河最少需要几条船
 */
public class Code01_MinBoat {

	// 请保证arr有序
	public static int minBoat(int[] arr, int limit) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		// 将无序数组进行排序
        Arrays.sort(arr);
        // arr中有人的体重超过(limit/2)则返回-1
        if (arr[arr.length-1] > limit){
            return -1;
        }
        int lessR = -1;
        // 所有人的体重都不超过limit，继续讨论
		// 找到 <= (limit)/2 的最右位置
		for (int i = arr.length - 1; i >= 0; i--) {
			if (arr[i] <= (limit / 2)) {
				lessR = i;
				break;
			}
		}
		if (lessR == -1) {
		    // 每个人的体重都超过(limit/2)，需要arr.length条船
			return arr.length;
		}
		// 一定有左右两个部分，左(<= limit/2) 右(> limit/2)
		int L = lessR;
		int R = lessR + 1;
		// 画X的数量统计，画对号的量(加工出来)
		int lessUnused = 0;
		while (L >= 0) {
		    // 此时的L，让R划过了几个数
			int solved = 0;
			while (R < arr.length && arr[L] + arr[R] <= limit) {
				R++;
				solved++;
			}
			// R来到的位置是第一个开始又不达标的位置
			if (solved == 0) {
				lessUnused++;
				L--;
			} else {// 此时的L，让R划过了solved(>0)个数
				L = Math.max(-1, L - solved);
			}
		}
		int lessAll = lessR + 1;// 左半区总个数  <= limit /2 的区域
		int lessUsed = lessAll - lessUnused; // 画对号的量
		int moreUnsolved = arr.length - lessR - 1 - lessUsed; // > limit/2 区中，没搞定的数量
		return lessUsed + ((lessUnused + 1) >> 1) + moreUnsolved;
	}

	public static void main(String[] args) {
		int[] arr = { 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5 };
		int weight = 6;
		System.out.println(minBoat(arr, weight));
	}

}
